package leetcode_1901_2000;

import com.sun.javafx.geom.Edge;

import java.util.Arrays;
import java.util.PriorityQueue;

public class LeeCode_1976 {
    public static void main(String[] args) {
//        System.out.println(countPaths(2, new int[][]{{1, 0, 10}}));
        System.out.println(countPaths(7,
                new int[][]{{0,6,7},{0,1,2},{1,2,3},{1,3,3},{6,3,3},{3,5,1},{6,5,1},{2,5,1},{0,4,5},{4,6,2}}));
    }
    private static int countPaths(int n, int[][] roads) {
        int[][] g = new int[n][n];
        long mod = (long) (1e9 + 7);
        for (int[] r : roads) {
            g[r[0]][r[1]] = r[2];
            g[r[1]][r[0]] = r[2];
        }
        boolean[] vis = new boolean[n];
        long[] dp = new long[n];
        dp[0] = 1;
        long[] dis = new long[n];
        Arrays.fill(dis, Long.MAX_VALUE);
        dis[0] = 0;
        PriorityQueue<long[]> queue = new PriorityQueue<>((o1, o2) -> (int) (o1[0] - o2[0]));
        queue.add(new long[]{0, 0});
        while (!queue.isEmpty()){
            long[] p = queue.poll();
            int now = (int) p[1];
            long d = p[0];
            if (vis[now])
                continue;
            vis[now] = true;
            for (int j = 0; j < n; j++) {
                if (g[now][j] == 0)
                    continue;
                long nd = d + g[now][j];
                if (nd < dis[j]){
                    dis[j] = nd;
                    dp[j] = dp[now];
                    queue.add(new long[]{nd, j});
                }else if (nd == dis[j]){
                    dp[j] = (dp[j] + dp[now]) % mod;
                }
            }
        }
        return (int) dp[n - 1];
    }
}
